package ds;
import java.util.ArrayList;
import java.util.List;
import java.util.HashMap;

public class MyGraph {
    private List<Integer>[] adj;
    public MyGraph(int n) {
        adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
    }
    public void addEdge(int u, int v) {
        adj[u].add(v);
        adj[v].add(u);
    }
    public List<Integer> getNeighbors(int u) {
        return adj[u];
    }

    // BFS: 返回从startId到targetId的最短路径（节点编号列表）
    public List<Integer> bfs(int startId, int targetId) {
        MyQueue queue = new MyQueue();
        HashMap<Integer, Integer> prev = new HashMap<>();
        queue.offer(startId);
        prev.put(startId, null);
        boolean found = false;
        while (!queue.isEmpty()) {
            int curId = (int) queue.poll();
            if (curId == targetId) {
                found = true;
                break;
            }
            for (int nbId : getNeighbors(curId)) {
                if (!prev.containsKey(nbId)) {
                    queue.offer(nbId);
                    prev.put(nbId, curId);
                }
            }
        }
        List<Integer> path = new ArrayList<>();
        if (found) {
            Integer cur = targetId;
            while (cur != null) {
                path.add(0, cur);
                cur = prev.get(cur);
            }
        }
        return path;
    }
} 